// 2025/10/25
// 添加与搜索单词 - 数据结构设计

class WordDictionary {
private:
    struct Node
    {
        Node() :end(false)
        {}
        bool end; // 当前结点是否为某个单词的结尾
        Node* next[26] = {nullptr}; // 下一个结点
    };
    Node* _root;

    static bool helper(Node* node, string& word, int pos)
    {
        if(node == nullptr) return false;
        if(pos == word.size()) return node->end;

        char ch = word[pos];
        if(ch == '.')
        {
            for(int i = 0; i < 26; i++)
            {
                if(helper(node->next[i], word, pos + 1))
                    return true;
            }
            return false;
        }
        else
        {
            return helper(node->next[ch - 'a'], word, pos + 1);
        }
    }
public:
    WordDictionary(Node* root = new Node) 
        :_root(root)
    {}
    
    void addWord(string word) {
        Node* cur = _root;
        for(auto& ch : word)
        {
            int pos = ch - 'a';
            if(cur->next[pos] == nullptr)
                cur->next[pos] = new Node;
            cur = cur->next[ch - 'a'];
        }
        cur->end = true;
    }
    
    bool search(string word) {
        return helper(_root, word, 0);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */